Quasi-Monte Carlo algorithms are studied for designing discreteapproximations of two-stage linear stochastic programs. Their integrands arepiecewise linear, but neither smooth nor lie in the function spaces consideredfor QMC error analysis. We show that under some weak geometric condition on thetwo-stage model all terms of their ANOVA decomposition, except the one ofhighest order, are smooth. Hence, Quasi-Monte Carlo algorithms may achieve theoptimal rate of convergence $O(n^{-1+\delta})$ with $\delta \in(0,\frac{1}{2}]$and a constant not depending on the dimension. The geometric condition is shownto be generically satisfied if the underlying distribution is normal. Wediscuss sensitivity indices, effective dimensions and dimension reductiontechniques for two-stage integrands. Numerical experiments show that indeedconvergence rates close to the optimal rate are achieved when using randomlyscrambled Sobol' point sets and randomly shifted lattice rules accompanied withsuitable dimension reduction techniques.
展开▼
